﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

namespace CharPointerTable
{
    public unsafe class StringTable
    {
        StringTableLive[] lives;

        public unsafe StringTable(Dictionary<string, int> strs)
        {
            int max = 0;
            Dictionary<int, Dictionary<string, int>> dict = new Dictionary<int, Dictionary<string, int>>();
            foreach (var item in strs)
            {
                if (!dict.ContainsKey(item.Key.Length))
                {
                    dict[item.Key.Length] = new Dictionary<string, int>();
                }
                dict[item.Key.Length][item.Key] = item.Value;
                if (max < item.Key.Length)
                {
                    max = item.Key.Length;
                }
            }

            lives = new StringTableLive[max + 1];
            foreach (var item in dict)
            {
                lives[item.Key] = new StringTableLive(item.Value, item.Key);
            }
        }
        public int Find(char* d, int length)
        {
            StringTableLive stringTableLive = lives[length];
            if (stringTableLive == null)
            {
                return -1;
            }
            return stringTableLive.Run(d);
        }

        internal unsafe class StringTableLive
        {
            unsafe ~StringTableLive()
            {
                if (isOne)
                {
                    Marshal.FreeHGlobal(allCharPtr);
                }
                else
                {
                    Marshal.FreeHGlobal(stackIntPtr);
                    Marshal.FreeHGlobal(allCharPtr);
                }
            }
            internal IntPtr stackIntPtr;
            internal IntPtr allCharPtr;
            internal Chake* chakes;
            internal int num;
            int oneData;
            bool isOne = false;
            char* oneChar;


            public unsafe StringTableLive(Dictionary<string, int> stringToIndex, int length)
            {
                if (stringToIndex.Count == 1)
                {
                    isOne = true;
                    num = length;
                    oneData = stringToIndex.First().Value;
                    allCharPtr = Marshal.AllocHGlobal((length + 1) * sizeof(char));
                    oneChar = (char*)allCharPtr.ToPointer();
                    string str = stringToIndex.First().Key;
                    for (int i = 0; i < str.Length; i++)
                    {
                        oneChar[i] = str[i];
                    }
                    oneChar[length] = '\0';
                    return;
                }
                string[] strs = new string[stringToIndex.Count];
                Dictionary<string, int> allCharIndex = new Dictionary<string, int>();
                int idd = 0;
                foreach (var item in stringToIndex)
                {
                    allCharIndex[item.Key] = idd;
                    strs[idd] = item.Key;
                    idd++;
                }

                ChakeNode root = new ChakeNode();

                root.strs = stringToIndex.Keys.ToArray();
                root.Division();

                List<ChakeNode> list = new List<ChakeNode>();
                List<ChakeNode> list2 = new List<ChakeNode>();
                root.Assignment(list);
                int chakeLength = 0;
                foreach (var item in list)
                {
                    if (item.strs.Length == 1)
                    {
                        item.dataIndex = stringToIndex[item.strs[0]];
                        item.charIndex = allCharIndex[item.strs[0]];
                    }
                    if (item.isLast == false)
                    {
                        item.index = list2.Count;
                        list2.Add(item);
                        ++chakeLength;
                    }
                }
                num = length;
                int size = num + 1;
                stackIntPtr = Marshal.AllocHGlobal(chakeLength * Marshal.SizeOf(typeof(Chake)));
                chakes = (Chake*)stackIntPtr.ToPointer();

                allCharPtr = Marshal.AllocHGlobal(stringToIndex.Count * size * sizeof(char));
                char* allChar = (char*)allCharPtr.ToPointer();

                for (int i = 0; i < stringToIndex.Count; i++)
                {
                    for (int j = 0; j < size - 1; j++)
                    {
                        char v = strs[i][j];
                        allChar[i * size + j] = v;
                        //*(allChar + i * size + j) = strs[i][j];
                    }
                    //*(allChar + i * size + size - 1) = '\0';
                    allChar[i * size + size - 1] = '\0';
                }


                ChakeTest[] chakes2 = new ChakeTest[chakeLength];
                for (int i = 0; i < chakes2.Length; i++)
                {
                    chakes2[i] = new ChakeTest();
                    chakes2[i].testIndex = i;
                }
                for (int i = 0; i < list2.Count; i++)
                {
                    ChakeNode node = list2[i];
                    chakes2[i].chakeIndex = node.chakeIndex;
                    chakes2[i].chakeValue = node.chakeValue;
                    if (node.next == null)
                    {
                        chakes2[i].next = null;
                        chakes2[i].data = allChar + node.charIndex;
                        chakes2[i].dataIndex = node.dataIndex;
                    }
                    else
                    {
                        chakes2[i].next = chakes2[node.next.index];
                    }
                    if (node.no.next == null && node.no.no == null)
                    {
                        chakes2[i].no = null;
                        chakes2[i].noData = allChar + node.no.charIndex;
                        chakes2[i].noDataIndex = node.no.dataIndex;
                    }
                    else
                    {
                        if (node.no.isLast)
                        {
                            chakes2[i].no = chakes2[node.no.next.index];
                        }
                        else
                        {
                            chakes2[i].no = chakes2[node.no.index];
                        }
                    }
                }

                for (int i = 0; i < list2.Count; i++)
                {
                    ChakeNode node = list2[i];
                    chakes[i].chakeIndex = node.chakeIndex;
                    chakes[i].chakeValue = node.chakeValue;
                    if (node.next == null)
                    {
                        chakes[i].next = null;
                        chakes[i].data = allChar + size * node.charIndex;
                        chakes[i].dataIndex = node.dataIndex;
                    }
                    else
                    {
                        chakes[i].next = &chakes[node.next.index];
                    }
                    if (node.no.next == null && node.no.no == null)
                    {
                        chakes[i].no = null;
                        chakes[i].noData = allChar + size * node.no.charIndex;
                        chakes[i].noDataIndex = node.no.dataIndex;
                    }
                    else
                    {
                        if (node.no.isLast)
                        {
                            chakes[i].no = &chakes[node.no.next.index];
                        }
                        else
                        {
                            chakes[i].no = &chakes[node.no.index];
                        }
                    }
                }

            }

            internal unsafe struct Chake
            {
                public int chakeIndex;
                public char chakeValue;

                public Chake* next;
                public Chake* no;

                public char* data;
                public char* noData;

                public int dataIndex;
                public int noDataIndex;
            }

            internal unsafe class ChakeTest
            {
                public int chakeIndex;
                public char chakeValue;

                public ChakeTest next;
                public ChakeTest no;

                public char* data;
                public char* noData;

                public int dataIndex;
                public int noDataIndex;
                public int testIndex;
            }

            public unsafe int Run(char* cha)
            {
                if (isOne)
                {
                    if (EqualsHelper(oneChar, cha))
                    {
                        return oneData;
                    }
                    return -1;
                }
                Chake* now = &chakes[0];
                while (true)
                {
                    if (cha[now->chakeIndex] == now->chakeValue)
                    {
                        if (now->next == null)
                        {
                            if (EqualsHelper(now->data, cha))
                            {
                                return now->dataIndex;
                            }
                            else
                            {
                                return -1;
                            }
                        }
                        else
                        {
                            now = now->next;
                        }
                    }
                    else
                    {
                        if (now->no == null)
                        {
                            if (EqualsHelper(now->noData, cha))
                            {
                                return now->noDataIndex;
                            }
                            else
                            {
                                return -1;
                            }
                        }
                        else
                        {
                            now = now->no;
                        }
                    }
                }
            }
            private unsafe bool EqualsHelper(char* ptr, char* ptr3)
            {
                long* ptr2 = (long*)ptr;
                long* ptr4 = (long*)ptr3;
                while (num >= 12)
                {
                    if (*ptr2 != *ptr4)
                    {
                        return false;
                    }
                    if (*(ptr2 + 1) != *(ptr4 + 1))
                    {
                        return false;
                    }
                    if (*(ptr2 + 2) != *(ptr4 + 2))
                    {
                        return false;
                    }
                    ptr2 += 3;
                    ptr4 += 3;
                    num -= 12;
                }
                while (num >= 4)
                {
                    if (*ptr2 != *ptr4)
                    {
                        return false;
                    }
                    ++ptr2;
                    ++ptr4;
                    num -= 4;
                }
                if (num == 0)
                {
                    return true;
                }
                if (num == 3)
                {
                    if (*(int*)ptr2 != *(int*)ptr4)
                    {
                        return false;
                    }
                    if (*((int*)ptr2 + 1) != *((int*)ptr4 + 1))
                    {
                        return false;
                    }
                }
                else
                {
                    if (*(int*)ptr2 != *(int*)ptr4)
                    {
                        return false;
                    }
                }
                return true;
            }

            internal class ChakeNode
            {
                public List<ChakeNode> nodes = new List<ChakeNode>();
                public int chakeIndex = -1;
                public char chakeValue;
                public ChakeNode next;
                public ChakeNode no;
                public bool isLast;
                public string[] strs;
                public int index = 0;
                public int dataIndex = -1;
                public int charIndex = -1;
                public ChakeNode()
                {
                }
                public override string ToString()
                {
                    if (isLast)
                    {
                        return chakeValue + " " + chakeIndex + " last";
                    }
                    return chakeValue + " " + chakeIndex;
                }
                public ChakeNode(char chakeValue, int chakeIndex)
                {
                    this.chakeValue = chakeValue;
                    this.chakeIndex = chakeIndex;
                }


                struct Data
                {
                    public string str;
                    public int index;
                    public Data(string str, int index)
                    {
                        this.str = str;
                        this.index = index;
                    }
                }

                public void Division()
                {
                    int nowIndex = chakeIndex;
                    Dictionary<char, List<string>> pairs = new Dictionary<char, List<string>>();
                    int size = strs[0].Length;
                    do
                    {
                        nowIndex++;
                        pairs = new Dictionary<char, List<string>>();
                        for (int i = 0; i < strs.Length; i++)
                        {
                            char key = strs[i][nowIndex];
                            if (pairs.ContainsKey(key))
                            {
                                pairs[key].Add(strs[i]);
                            }
                            else
                            {
                                pairs[key] = new List<string>();
                                pairs[key].Add(strs[i]);
                            }
                        }
                    } while (pairs.Count == 1);
                    pairs = pairs.OrderByDescending(x => x.Value.Count).ToDictionary(x => x.Key, x => x.Value);

                    foreach (var item in pairs)
                    {
                        ChakeNode chakeNode = new ChakeNode();
                        chakeNode.chakeIndex = nowIndex;
                        chakeNode.chakeValue = item.Key;
                        chakeNode.strs = item.Value.ToArray();
                        if (chakeNode.strs.Length > 1)
                        {
                            chakeNode.Division();
                        }
                        nodes.Add(chakeNode);
                    }
                }

                public void Assignment(List<ChakeNode> list)
                {
                    if (nodes.Count > 0)
                    {
                        for (int i = 0; i < nodes.Count - 1; i++)
                        {
                            nodes[i].no = nodes[i + 1];
                            if (nodes[i].nodes.Count > 0)
                            {
                                nodes[i].next = nodes[i].nodes[0];
                            }
                            list.Add(nodes[i]);
                            nodes[i].Assignment(list);
                        }

                        if (nodes[nodes.Count - 1].nodes.Count > 0)
                        {
                            nodes[nodes.Count - 1].next = nodes[nodes.Count - 1].nodes[0];
                        }
                        list.Add(nodes[nodes.Count - 1]);
                        nodes[nodes.Count - 1].isLast = true;
                        nodes[nodes.Count - 1].Assignment(list);
                    }
                }


            }

        }
    }
}
